package kyssion.introductionToAlgorithms.chapter_02;

/**
 * 问题描述,在s中找到两个数字可以让和为X 要求时间是n*lgn
 */
public class Alorithms003_2_3_7q_在S中找到两个数和为X {
    public static void main(String[] args) {
        System.out.println(new Alorithms003_2_3_7q_在S中找到两个数和为X().ans(
                new int[]{
                        1,1,1,1,1,1,1,2
                },3
        ));
    }

    /**
     * 使用归并排序的实现实现对应的
     * @param s
     * @param x
     * @return
     */

    public boolean ans(int[] s, int x) {
        return find(s, x, 0, s.length - 1);
    }

    private boolean find(int[] s, int x, int start, int end) {
        if (start > end) {
            return false;
        }
        if (start == end) {
            return s[start] == x;
        }

        //start = 0 end = 1 midle = 0
        int midle = (start + end) >> 1;
        if (find(s, x, start, midle)) {
            return true;
        }

        if (find(s, x, midle + 1, end)) {
            return true;
        }

        int left = start;
        int right = midle + 1;
        int speed = end - start;
        int i = 0;
        while (i < speed) {
            if (s[left] + s[right] > x) {
                return false;
            } else if (s[left] + s[right] == x) {
                return true;
            } else {
                if (s[left] + s[right] > x) {
                    return false;
                } else if (s[left] + s[right] == x) {
                    return true;
                } else {
                    if (left == midle && right == end) {
                        break;
                    } else if (left == midle) {
                        right++;
                    } else {
                        left++;
                    }
                }
            }
            i++;
        }
        return s[midle] + s[end] == x;
    }
}
